// https://leetcode.cn/problems/ipo/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 将资本和利润组合并按资本需求排序
// 2. 使用大根堆维护当前可执行项目的利润
// 3. 每次选择利润最大的项目执行，更新资本
// 4. 利用排序和堆优化项目选择过程
// 5. 时间复杂度：O(NlogN + KlogN)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>

class Solution 
{
public:
    typedef pair<int, int> PII;
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) 
    {
        int n = profits.size();

        vector<PII> arr;
        for (int i = 0 ; i < n ; i++)
        {
            arr.push_back({capital[i], profits[i]});
        }
        sort(arr.begin(), arr.end(), [&](const PII& p1, const PII& p2){
            return p1.first < p2.first;
        });

        int cur = 0;
        priority_queue<int> maxHeap;
        for (int i = 0 ; i < k ; i++)
        {
            while (cur < n && arr[cur].first <= w)
            {
                maxHeap.push(arr[cur].second);
                cur++;
            }
            if (!maxHeap.empty())
            {
                int profit = maxHeap.top();
                w += profit;
                maxHeap.pop();
            }
            else
            {
                break;
            }
        }

        return w;
    }
};

int main()
{
    vector<int> profits1 = {1,2,3}, profits2 = {1,2,3};
    vector<int> capital1 = {0,1,1}, capital2 = {0,1,2};

    int k1 = 2, k2 = 3;
    int w1 = 0, w2 = 0;

    Solution sol;

    cout << sol.findMaximizedCapital(k1, w1, profits1, capital1) << endl;
    cout << sol.findMaximizedCapital(k2, w2, profits2, capital2) << endl;

    return 0;
}